package _10_binary_tree.order.depth;

import _10_binary_tree.TreeNode;
import org.junit.Test;

import java.util.LinkedList;

/**
 * @author: mornd
 * @dateTime: 2023/6/11 - 17:28
 * 前，中，后序遍历方法分开
 */
public class MyTest2_2 {
    /**
     * 构建树
     *          1
     *         /\
     *        2  3
     *       /\  /\
     *      4 7 5  6
     * @return
     */
    static TreeNode genericTestTree() {
        return new TreeNode(1, new
                TreeNode(2,
                new TreeNode(4), new TreeNode(7)),
                new TreeNode(3,
                        new TreeNode(5),
                        new TreeNode(6)));
    }

    @Test
    public void test() {
        // 1,2,4,7,3,5,6
        System.out.print("前序遍历结果：");
        preOrder(genericTestTree());
        // 4,2,7,1,5,3,6
        System.out.print("\n中序遍历结果：");
        inOrder(genericTestTree());
        // 4,7,2,5,6,3,1
        System.out.print("\n后序遍历结果：");
        postOrder(genericTestTree());
    }

    // 前序
    void preOrder(TreeNode root) {
        TreeNode curr = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        while (curr != null || !stack.isEmpty()) {
            if(curr != null) {
                stack.push(curr);
                System.out.print(curr + " ");
                curr = curr.left;
            } else {
                // 走到这一步说明左子树都走完了
                TreeNode pop = stack.pop();
                curr = pop.right;
            }
        }
    }

    // 中序
    void inOrder(TreeNode root) {
        TreeNode curr = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        while (curr != null || !stack.isEmpty()) {
            if(curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode pop = stack.pop();
                System.out.print(pop + " ");
                curr = pop.right;
            }
        }
    }

    // 后序
    void postOrder(TreeNode root) {
        TreeNode curr = root;
        LinkedList<TreeNode> stack = new LinkedList<>();

        // 记录当前节点的右子节点
        TreeNode rightSonNode = null;
        while (curr != null || !stack.isEmpty()) {
            if(curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                /*
                    如果我的右子节点没有值了，或者
                    我的右子节点是上一个弹栈的元素，那么就表示我的右子节点都已经遍历到了，那么我也要弹出
                 */
                if(peek.right == null || peek.right == rightSonNode) {
                    rightSonNode = stack.pop();
                    System.out.print(rightSonNode + " ");
                } else {
                    curr = peek.right;
                }
            }
        }
    }
}
